﻿using System.Text;
/// <summary>
/// https://leetcode-cn.com/problems/n-queens/
/// </summary>
public class Solution
{
    private class Board
    {
        /// <summary>
        /// 用 <c>null</c> 表示这里有皇后，<code>true</code> 表示可以放这里不会被其他皇后吃，<code>false</code> 表示不可以放。
        /// </summary>
        private readonly bool?[,] board;

        private readonly (int x, int y) nextPlace;

        public int Size => this.board.GetLength(0);
        public Board(int size)
            : this(size, (0, 0), true) { }
        private Board(int size, (int x, int y) nextPlace, bool setToTrue)
        {
            this.nextPlace = nextPlace;
            this.board = new bool?[size, size];
            if (setToTrue)
            {
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                        this.board[i, j] = true;
                }
            }
        }

        public Board PutQueenOnNewBoard(int x, int y)
        {
            var size = this.Size;
            var copy = new Board(size, (x, y + 1), false);
            Array.Copy(this.board, copy.board, this.board.Length);

            for (int i = x + 1, j = y + 1; i < size && j < size; i++, j++)
                copy.board[i, j] = false;

            for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--)
                copy.board[i, j] = false;

            for (int i = x - 1, j = y + 1; i >= 0 && j < size; i--, j++)
                copy.board[i, j] = false;

            for (int i = x + 1, j = y - 1; i < size && j >= 0; i++, j--)
                copy.board[i, j] = false;

            for (int i = 0; i < size; i++)
                copy.board[i, y] = false;

            for (int j = 0; j < size; j++)
                copy.board[x, j] = false;

            copy.board[x, y] = null;

            return copy;
        }

        public IEnumerable<string> ToStrings()
        {
            for (int i = 0; i < this.board.GetLength(0); i++)
            {
                StringBuilder stringBuilder = new StringBuilder();
                for (int j = 0; j < this.board.GetLength(1); j++)
                    _ = stringBuilder.Append(this.board[i, j] == null ? 'Q' : '.');
                yield return stringBuilder.ToString();
            }
        }

        public IEnumerable<(int x, int y)> AvailablePositionsAfterLastPlace
        {
            get
            {
                for (int j = this.nextPlace.y; j < this.board.GetLength(1); j++)
                {
                    if (this.board[this.nextPlace.x, j] == true)
                        yield return (this.nextPlace.x, j);
                }

                for (int i = this.nextPlace.x + 1; i < this.board.GetLength(0); i++)
                {
                    for (int j = 0; j < this.board.GetLength(1); j++)
                    {
                        if (this.board[i, j] == true)
                            yield return (i, j);
                    }
                }
            }
        }
    }

    private IEnumerable<Board> PutAQueen(IEnumerable<Board> boards)
    {
        foreach (var board in boards)
        {
            foreach (var (x, y) in board.AvailablePositionsAfterLastPlace)
                yield return board.PutQueenOnNewBoard(x, y);
        }
    }

    public IList<IList<string>> SolveNQueens(int n)
    {
        IEnumerable<Board> boards = new Board[] { new Board(n) };
        for (int i = 0; i < n; i++)
            boards = this.PutAQueen(boards);
        var linq = from board in boards
                   select (IList<string>)(board.ToStrings().ToList());
        return linq.ToList();
    }
}

/* 下方案超时
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Text;
/// <summary>
/// https://leetcode-cn.com/problems/n-queens/
/// </summary>
public class Solution
{
    private class Board
    {
        public class Comparer : IEqualityComparer<Board>
        {
            public bool Equals(Board? x, Board? y)
            {
                var size = x?.Size;
                if (size != y?.Size)
                    return false;
                if (size is null)
                    return y is null;
                if (y is null)
                    return false;
                Debug.Assert(x is not null);

                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        if (x.board[i, j] != y.board[i, j])
                            return false;
                    }
                }
                return true;
            }

            public int GetHashCode([DisallowNull] Board obj)
            {
                var size = obj.Size;
                HashCode hashCode = new HashCode();
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                        hashCode.Add(obj.board[i, j]);
                }
                return hashCode.ToHashCode();
            }
        }


        /// <summary>
        /// 用 <c>null</c> 表示这里有皇后，<code>true</code> 表示可以放这里不会被其他皇后吃，<code>false</code> 表示不可以放。
        /// </summary>
        private readonly bool?[,] board;
        public int Size => board.GetLength(0);
        public Board(int size)
            : this(size, true) { }
        private Board(int size, bool setToTrue)
        {
            this.board = new bool?[size, size];
            if (setToTrue)
            {
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                        this.board[i, j] = true;
                }
            }
        }

        public Board PutQueenOnNewBoard(int x, int y)
        {
            var size = this.Size;
            var copy = new Board(size, false);
            Array.Copy(this.board, copy.board, this.board.Length);

            for (int i = x + 1, j = y + 1; i < size && j < size; i++, j++)
                copy.board[i, j] = false;

            for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--)
                copy.board[i, j] = false;

            for (int i = x - 1, j = y + 1; i >= 0 && j < size; i--, j++)
                copy.board[i, j] = false;

            for (int i = x + 1, j = y - 1; i < size && j >= 0; i++, j--)
                copy.board[i, j] = false;

            for (int i = 0; i < size; i++)
                copy.board[i, y] = false;

            for (int j = 0; j < size; j++)
                copy.board[x, j] = false;

            copy.board[x, y] = null;

            return copy;
        }

        public IEnumerable<string> ToStrings()
        {
            for (int i = 0; i < board.GetLength(0); i++)
            {
                StringBuilder stringBuilder = new StringBuilder();
                for (int j = 0; j < board.GetLength(1); j++)
                    _ = stringBuilder.Append(board[i, j] == null ? 'Q' : '.');
                yield return stringBuilder.ToString();
            }
        }

        public IEnumerable<(int x, int y)> AvailablePositions
        {
            get
            {
                for (int i = 0; i < board.GetLength(0); i++)
                {
                    for (int j = 0; j < board.GetLength(1); j++)
                    {
                        if (board[i, j] == true)
                            yield return (i, j);
                    }
                }
            }
        }
    }

    private IEnumerable<Board> PutAQueen(IEnumerable<Board> boards)
    {
        foreach (var board in boards)
        {
            foreach (var (x, y) in board.AvailablePositions)
                yield return board.PutQueenOnNewBoard(x, y);
        }
    }

    public IList<IList<string>> SolveNQueens(int n)
    {
        IEnumerable<Board> boards = new Board[] { new Board(n) };
        var comparer = new Board.Comparer();
        for (int i = 0; i < n; i++)
            boards = PutAQueen(boards).Distinct(comparer);
        var linq = from board in boards
                   select (IList<string>)(board.ToStrings().ToList());
        return linq.ToList();
    }
}
*/